package LeetCode_234;


import java.util.Collections;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2023/3/23 18:51
 */
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public static void main(String[] args) {
        ListNode node5 = new ListNode(5,null);
        ListNode node4 = new ListNode(4,node5);
        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(1,node2);
        Solution.isPalindrome(node1);
    }

    public static ListNode turnAll(ListNode head) {

        ListNode cur = head;
        ListNode prev = null;   //指向cur的上一个结点
        while (cur != null) {

            ListNode res = cur.next;  //提前保存cur的下一个结点
            cur.next = prev;
            prev = cur;
            cur = res;
        }
        return prev;

    }

    public static boolean isPalindrome(ListNode head) {
        //1.将整个链表反转，然后比较
        //2.反转其中的一半链表，然后比较
        if (head.next == null) {
            return true;
        }
        ListNode copyList = new ListNode();

        ListNode cur = turnAll(head);
        ListNode res = head;
        while (res != null && cur != null) {
            if (res.val != cur.val) {
                return false;
            }
            cur = cur.next;
            res = res.next;
        }
        return true;
    }

}
